package com.zklh.leetcode.top100;

/**
 * 缺失的第一个正数
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/20
 */
public class Solution41 {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = n+1;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i])-1] = - Math.abs(nums[Math.abs(nums[i])-1]);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }

    public static void main(String[] args) {
        Solution41 solution41 = new Solution41();
        int[] nums = {7,8,9,11,12};

        System.out.println(solution41.firstMissingPositive(nums));
    }
}